package leetcode.code2106;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int maxTotalFruits(int[][] fruits, int startPos, int k) {
		int len = fruits.length;
		int max = startPos, min = startPos;
		for (int i = 0; i < fruits.length; i++) {
			max = Math.max(max, fruits[i][0]);
			min = Math.min(min, fruits[i][0]);
		}
		int[] poses = new int[max + 1];
		for (int i = 0; i < len; i++) {
			poses[fruits[i][0]] = fruits[i][1];
		}
		long[] sums = this.presum(poses);
		int L = Math.max(min, startPos - k), R = Math.min(startPos + k, max);
		long ans = 0;
		for (int l = L; l <= startPos && l <= R; l++) {
			int r = Math.min(k - (startPos - l) * 2 + startPos, R);
			ans = Math.max(ans, this.sumIndex(sums, l, r));
		}
		for (int r = R; r >= startPos && r >= L; r--) {
			int l = Math.max(startPos - (k - (r - startPos) * 2), L);
			ans = Math.max(ans, this.sumIndex(sums, l, r));
		}
		return (int) ans;
	}

	public long[] presum(int[] nums) {
		int len = nums.length;
		long[] sums = new long[len + 1];
		for (int i = 1; i < sums.length; i++) {
			sums[i] = sums[i - 1] + nums[i - 1];
		}
		return sums;
	}

	public long sumIndex(long[] sums, int indexL, int indexR) {
		return sums[indexR + 1] - sums[indexL];
	}

	@Override
	public void debug4() {
		H.compare(31, this.maxTotalFruits(H.str2array1("[[1,4],[3,7],[4,8],[6,5],[10,3],[12,8],[13,6],[14,5],[16,3],[18,7],[22,7],[24,1],[28,7],[32,3],[34,7],[35,7],[37,7],[40,7]]"), 41, 10));
		H.compare(10000, this.maxTotalFruits(H.str2array1("[[0,10000]]"), 200000, 200000));
		H.compare(10000, this.maxTotalFruits(H.str2array1("[[200000,10000]]"), 200000, 200000));
		H.compare(71, this.maxTotalFruits(H.str2array1(
				"[[0,7],[7,4],[9,10],[12,6],[14,8],[16,5],[17,8],[19,4],[20,1],[21,3],[24,3],[25,3],[26,1],[28,10],[30,9],[31,6],[32,1],[37,5],[40,9]]"),
				21, 30));
		H.compare(10000, this.maxTotalFruits(H.str2array1("[[200000,10000]]"), 200000, 0));
		H.compare(14, this.maxTotalFruits(H.str2array1("[[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]]"), 5, 4));
		H.compare(9, this.maxTotalFruits(H.str2array1("[[2,8],[6,3],[8,6]]"), 5, 4));
		H.compare(0, this.maxTotalFruits(H.str2array1("[[0,3],[6,4],[8,5]]"), 3, 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
